Section: New Results

Covering problems

In [5], we study a covering problem where vertices of a graph have to be covered by rooted sub-trees. We present three mixed-integer linear programming models, two of which are compact while the other is based on Dantzig-Wolfe decomposition. In the latter case, we focus on the column generation sub-problem, a knapsack problem with precedence constraints on trees, for which we propose several algorithms among them a branch and bound algorithm and various dynamic programs. Numerical results are obtained using instances from the literature and instances based on a real-life districting application. Experiments show that the branch-and-price algorithm is able to solve much bigger instances than the compact model, which is limited to very small instance sizes.